package com.ankie.algorithm;

import com.sun.source.tree.Tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * BST 树的序列化与反序列化，LeetCode 297题，这里采用的方式是前序遍历的方式
 * @author :  ankie
 * Create at:  2020/6/24 11:25
 * Copyright: (c)2019 AIR Times Inc. All rights reserved.
 * @version : 1.0
 */
public class SerializeAndDeserializeBST {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder str = new StringBuilder();
        str.append("[");
        str = buildStr(root, str);
        String result = str.toString().substring(0, str.toString().length() - 1);
        return result + "]";
    }

    public StringBuilder buildStr(TreeNode root, StringBuilder str) {
        if (root == null) {
            return str.append("null,");
        } else {
            str.append(root.val).append(",");
            buildStr(root.left, str);
            buildStr(root.right, str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        data = data.substring(1, data.length() -1);
        String[] arr = data.split(",");
        List<String> list = new LinkedList<String>(Arrays.asList(arr));
        return buildTree(list);
    }

    private TreeNode buildTree(List<String> list) {
        if (list.get(0).equals("null")) {
            list.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        root.left = buildTree(list);
        root.right = buildTree(list);
        return root;
    }

    public static void main(String[] args) {
//        int[] arr = new int[]{2,1,3};
        String data = "[1,2,null,null,3,4,null,null,5,null,null]";
        System.out.println(data);
        SerializeAndDeserializeBST serialize = new SerializeAndDeserializeBST();
        System.out.println("---- 分割线 ----");
        TreeNode root = serialize.deserialize(data);
        System.out.println(serialize.serialize(root));
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.right.left = new TreeNode(4);
//        root.right.right = new TreeNode(5);
//        System.out.println(serialize.serialize(root));
    }
}
